Not Applicable.
Not Applicable.
Files of instructions known as xe2x80x9cprogramsxe2x80x9d are used to control the operation of various types of hardware components, including microprocessors and/or application specific integrated circuits (ASICs). Often, a program is initially written in a high level language such as C++ or PASCAL, and then converted by a compiler program into a lower level representation sometimes known as assembler language. The instructions of the assembler language program can be executed by the target system. Such a programming model generally requires that the program be fully written or generated prior to being executed to do the work it is designed to perform.
However, in certain situations, it is either undesirable or unfeasible to provide a complete program before a system in which the program executes begins operation. This type of situation may arise, for example, where the number of possibilities that must be addressed by the system is so large that a complete program file designed to handle all situations would be prohibitively large. Another way of looking at this category of problems is that the specific program requirements are not known until execution time. A program designed to handle all possible requirements that may arise would be wasteful, and difficult to modify or extend. It may also be desirable to limit program size in order to conserve memory resources used to store the program.
For example, lack of hardware resources, as may be found in embedded systems which are designed to perform a specific task in real-time, may limit the amount of space available to store the program. Embedded systems are often employed in networking and communications systems such as forwarding devices. A forwarding device is any device which forwards data units from ports on which they are received to ports from which they are re-transmitted, in accordance with some well-defined topology management protocol. Examples of well-defined topology management protocols include Border Gateway Protocol 4 (BGP4), Open Shortest Path First (OSPF), or DVMRP (Distance Vector Multicast Routing Protocol. During its operation, the forwarding device modifies the received data units in order to perform routing and format translations on a per-information flow basis. Each information flow is considered to be a mapping of an input port to one or more output ports according to data unit header information in the received data unit.
The number of combinations of data unit input formats and output formats that must potentially be processed in a forwarding device is very large. Accordingly, a program which would handle all possible combinations of input and output formats, including necessary modifications of data unit header field contents, is extremely large and complicated, making it difficult to support or extend, and costly in terms of storage requirements.
In addition, typical compiler technology has placed an emphasis on performing many optimizations while generating the assembler language program. This arises from the desire to trade off time spent during compilation for assembler code which is fast and compact. However, this approach does not consider any possibility of generating assembler code in real-time, while the system itself is operating. In particular, where functionality must be modified on a xe2x80x9cjust in timexe2x80x9d basis, for example in response to receipt of new information flow, code generation based on existing compilers would be undesirably slow, and result in excessive data unit queuing, causing poor performance.
For the above reasons, it would be desirable to have a system for generating an assembler language program in real-time in response to program requirements that are determined during system operation. The system should be fast enough to generate assembler code to handle new operational requirements as they are received. Moreover, the system should be applicable to generation of a program which is capable of performing data unit format and header content conversion and modification in a forwarding device implementation.
In accordance with the present invention, there is disclosed a system for automatic program generation which receives a number of input format descriptors and a number of output format descriptors. The system generates a program for converting an input data sequence having a format described by the input format descriptors to an output data sequence having a format described by the output format descriptors. The program may be generated, loaded, and then executed in response to receipt of an input data stream, wherein a portion of the input data stream corresponds to the input data sequence. The input data sequence and output data sequence consist of a number of data type indicators.
In an exemplary embodiment, each layer of a communications protocol stack is represented by 0 or more format descriptors. Examples of well known protocol stacks include the IP protocol stack, the DECNet protocol stack, and the AppleTalk protocol stack. Similarly, each field within a data unit is represented by 0 or more data type indicators. Accordingly, the input data type indicators may correspond to fields of data units received by a forwarding device, and the output data type indicators may correspond to fields of corresponding data units forwarded by the forwarding device. In the exemplary embodiment, the generated program is executed on a hardware processor to convert a data unit that is received on a first communication link into an output data unit for transmission on a second communication link. Generation and loading of the program may be triggered by receipt of an initial data unit for a particular information flow.
The generated program, for example, converts a received data unit in the well known Ethernet format to an output data unit in the similarly well known IP over ATM format, or vice versa, as appropriate for the specific information flow.
Thus there is disclosed a system for generating an assembler language program in real-time in response to program requirements that are determined during system operation. The system is fast enough to generate assembler code to handle new operational requirements as they are received. Moreover, the system is well suited to generation of a program which is capable of performing data unit format and header content conversion and modification in a forwarding device implementation.